package gold.contest;

import gold.utils.InputUtil;
import gold.vo.TreeNode;
import javafx.util.Pair;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC6057 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        int ans = 0;

        public int averageOfSubtree(TreeNode root) {
            getSubCnt(root);
            return ans;
        }

        public Pair<Integer, Integer> getSubCnt(TreeNode root) {
            if (null == root) return new Pair<>(0, 0); // first:node sum, second, node cnt.
            Pair<Integer, Integer> leftSide = getSubCnt(root.left);
            Pair<Integer, Integer> rightSide = getSubCnt(root.right);
            if ((leftSide.getKey() + rightSide.getKey() + root.val) / (leftSide.getValue() + rightSide.getValue() + 1) == root.val)
                ans++;
            return new Pair<>(leftSide.getKey() + rightSide.getKey() + root.val, leftSide.getValue() + rightSide.getValue() + 1);
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.averageOfSubtree(TreeNode.createTree("[4,8,5,0,1,null,6]")));
        System.out.println(solution.averageOfSubtree(TreeNode.createTree("[2]")));
    }

    public static void main(String[] args) throws Exception {
        LC6057 an = new LC6057();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
